package airthmetic.exercise.dp;

// 经典dp的0-1背包问题
//1.1、问题描述
//      给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]。
//      现在让你用这个背包装物品，每种物品可以选0个或1个，问最多能装的价值是多少？
public class BackPack3 {
    /**
     *
     * @param wt 每个物品的重量 即wt[i]是第i个物品的重量
     * @param v  每个物品的价值 即v[i]是第i个物品的价值
     * @param N  物品个数
     * @param W  背包重量
     * @return 最多能装多少价值
     */
    public static int dp(int[] wt, int[] v, int N, int W) {
        /**
         * 因为问题具备重叠子问题和无后效性以及最优子结构。 动态规划！
         * 动态规划思考问题：
         *  什么是原问题 什么是子问题
         *  原问题 W容量 N物品
         *  子问题 W-1容量 N-1物品
         *
         *  1.确认状态参数和选择
         *      状态参数：此题两个 物品数量和背包重量
         *
         *      选择/决策: 不断选择不同的物品数量和背包重量
         *
         *  2.定义 dp table含义
         *      int[][] dp = new int[N+1][W+1];
         *      dp[i][w] 表示 前i个物品在w重量下可以存放的最大价值
         *
         *  3.初始化 dp table
         *      i=0时 表示0个物品 此时背包能装的价值只能是不装物品 为0
         *      w=0时 表示背包为0容量 此时i为任何数量物品,背包可装容量都是0
         *
         *  4.推导状态转移公式
         *      for(int i=1; i<=N; i++){
         *          for(int w=1; w<=W; w++){
         *              if(wt[w-1] > v[i-1]){
         *                   dp[i][j] = dp[i-1][wt[j-1] - W] + v[j-1];
         *              }else{
         *                  dp[i][j] = dp[i][j-1];
         *
         *              }
         *          }
         *      }
         */

        int[][] dp = new int[N+1][W+1];
        for(int i=1; i<=N; i++){
           for(int w=1; w<=W; w++){
              if(wt[i-1] > w){
                  dp[i][w] = dp[i-1][w];
              }else{ // 放入物品或者不放入物品
                  dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-wt[i-1]]+ v[i-1]);
              }
           }
        }

        return dp[N][W];
    }



    /**
     *
     * @param wt 每个物品的重量 即wt[i]是第i个物品的重量
     * @param v  每个物品的价值 即v[i]是第i个物品的价值
     * @param N  物品个数
     * @param W  背包重量
     * @return 最多能装多少价值
     */
    public static int dp2(int[] wt, int[] v, int N, int W) {

        int[] dp = new int[W+1];
        for(int i=1; i<=N; i++){
            for(int w=1; w<=W; w++){
                if(wt[i-1] <= w){
                    // 放入物品或者不放入物品
                    dp[w] = Math.max(dp[w], dp[w-wt[i-1]]+ v[i-1]);
                }
            }
        }

        return dp[W];
    }

    public static void main(String[] args) {
        int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
        int[] wt = {3, 2, 1}; // 物品的重量
        int[] v = {5, 2, 3}; // 物品的价值
        System.out.println(new BackPack3().dp(wt,v,N,W));
    }
}
